Public key cryptosystems use a pair of asymmetric related keys, one for encryption and the other for decryption. Encryption in this context does not necessarily imply that the result is confidential, since data encrypted with a private key can be decrypted by anyone holding the public key—which may be widely available. One of the key pair, the private key, is kept secret by the user, while the other key, the public key, can be publicly disclosed. The key pair must have the property that, given knowledge of the public key, it is infeasible to determine the private key.
A user receives or, with suitable hardware or software, can generate for itself a pair of keys which are generally two large numbers. The user keeps one of these keys private and never discloses it. The other can be safely made public, just like a phone number or similar personal data. Due to the way the keys are generated, information encrypted with the private key can only be decrypted with the public key and vice versa. Using a key pair means that the sender and receiver do not need to share a secret key.
Public keys do not have to be published to the world. They can be shared as widely or narrowly as business and privacy requirements dictate.
The term “user” is defined as any entity including individuals, groups of individuals, one or more individuals in a role, corporations, organisations, computer applications or systems, automated machines, etc.
Public key cryptography makes the following possible:    Anyone knowing the user's public key can send the user a message encrypted with that key and can be sure that only the user—who alone has the corresponding private key—can decrypt it. This provides confidentiality.    The user might also encrypt a message with his private key. This cannot provide confidentiality, because anyone who knows the corresponding public key can decrypt it. But the fact that they can decrypt it means the message must have come from the user—who alone has the private key. This provides authentication and can also be used as a basis for non-repudiation—the digital equivalent of a signature.    If a sender signs a message with his own private key and then encrypts it with the recipient's public key, confidentiality, authentication and non-repudiation are provided together.
In practice, things are actually more complex. In the first situation, for performance and operational reasons, the sender will choose a random symmetric session key and a symmetric cipher to encrypt the message. The public key will be used to encrypt just the session key.
In the second situation above, a message is signed with a private key and this is known as a digital signature. One problem with signature methods is that cryptography can be slow due to the processing and communications overheads required. The volume of data sent is at least double the size of the original message.
Confidentiality may not be required and it may be desirable to be able to send signed plaintext messages. A method can be used that does not require the entire message to be encrypted and therefore reduces processing and communication overheads. This method is based on obtaining a “digest” of the message the user wishes to sign. One form of obtaining a message digest is a hash function. A hash function is a one-way function which maps an arbitrarily long piece of plain text into a comparatively small fixed-length bit string which is the message digest.
The hash function has the property that if the message is changed in anyway an entirely different value of message digest is produced by the hash function. It should also not be possible to generate two messages that have the same message digest. Given P (plaintext) it should be easy to compute H(P) (hash of the plaintext). Given H(P) it should be effectively impossible to find P (the original plaintext).
In the second situation, the hash function is used to generate a message digest from the content of the message to be signed. The message digest is then encrypted using the private key of a key pair to obtain the signature. The original plaintext message is transmitted together with the signature.
A recipient of the message uses the same hash function to obtain a digest of the plaintext message that has been received. The recipient also decrypts the signature using the public key of the key pair and obtains the message digest which was sent by the originator. The recipient compares the two digests and if they are the same, the signature is verified and the recipient is assured of the integrity and authenticity of the message.
FIG. 1 illustrates this prior art method of signing using a public key cryptography system. An originator 102 wishes to send a message 106 to a recipient 104. The originator 102 uses a hash function 108 to obtain a digest 110 of the message 106. The digest 110 is then encrypted 112 using the originator's 102 private key to obtain a signature 114. The originator 102 sends the message 106 and the signature 114 to the recipient 104.
The recipient 104 applies the same hash function 108 to the message 106 it has received to obtain a digest 118. The recipient also decrypts 120 the signature 114 it has received using the originator's public key. The decrypted signature is the digest 110 made by the originator 102. The digest 110 obtained by decrypting the signature is compared 124 to the digest 118 made by the recipient. If the two digests are the same, the message 106 has been verified by the signature.
As a separate process, authentication of a user can be carried out by a “challenge-response” procedure. The challenge-response procedure may be provided as an authentication protocol in the surrounding communications protocol such as the network-layer protocol or application-layer protocol. The user to be authenticated sends a message to the system that makes the authentication indicating that it wishes to open communication. The system sends a random value called a challenge to the user. The random value is different for each authentication request. The user encrypts the random value using its private key and sends the encrypted version back to the system. The system decrypts the version using the public key corresponding to the private key and verifies that the user is who it says it is. Communication can then commence between the user and the system.
The known challenge-response procedure is illustrated in FIG. 2. A user, Alice, 202 wishes have access to Bob 204 and Bob 204 wishes to authenticate that the user Alice 202 is not an impostor before granting access. Alice 202 sends a request 206 to Bob 204 to log on. Bob responds by creating 208 a challenge 210 and sending the challenge 210 to Alice 202 asking her to encrypt 212 the challenge 210.
Alice 202 encrypts 214 the challenge 210 with her private key and sends the signed challenge 216 to Bob 204. Bob 204 decrypts 218 the signed challenge 216 with Alice's public key. If the decrypted challenge is the same as the original challenge 210, Bob 204 approves access 220 to Alice 202.
Bob 204 may apply a hash function to the challenge 210 to obtain a digest and may send the digest to Alice 202 to encrypt with her signature.
If a user uses a single private key for both signing messages and challenge-response authentication, there is a risk that a challenge may be used to obtain a forged signature. If the challenge that is sent is not a random value but is a message digest obtained, for example, by applying a hash function to a message, the user wishing to be authenticated will apply his signature to the message digest and send the signed digest back to the authenticating system. For example, what is thought to be a random sequence could be a cheque sequence and signing the sequence would be signing the cheque, or a digest of the cheque.
In this way, a user may encrypt what it thinks is a random challenge but is actually the digest of a message of value, thus inadvertently signing the message. There is also a danger that a user can deny signing a message by claiming that the signature had been obtained by this forgery method.
The conventional solution to the above problem is to use two separate key pairs for each of signature and authentication. This has the disadvantage of extra maintenance of the keys including administrative tasks to manage two different key pairs and their associated certificates. This is particularly a problem if hardware tokens such as smart cards are used which have limited storage capabilities.
It is an aim of the present invention to enable the use of a single key pair for both signature and authentication by providing a safeguard against forgery of signed messages obtained during authentication.